package leetcode.problems;

import org.junit.Test;

/**
 * Created by gmwang on 2020/2/2
 * Sum of Nodes with Even-Valued Grandparent
 * 偶数的祖父节点的和
 */
public class SumofNodeswithEvenValuedGrandparent {
    /**
     * Given a binary tree, return the sum of values of nodes with even-valued grandparent.
     *
     * (A grandparent of a node is the parent of its parent, if it exists.)
     *
     * If there are no nodes with an even-valued grandparent, return 0.
     *
     *
     *
     * Example 1:
     *            6
     *          /   \
     *         7     8
     *        / \   / \
     *       2  7  1   3
     *      /  / \      \
     *     9  1   4      5
     *
     *
     * Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
     * Output: 18
     * Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.
     * 6.8 是偶数值的祖父节点，该祖父节点的子孙节点值的和，2+7+1+3+5 = 18
     **/
    public int sumEvenGrandparent(TreeNode root) {
        int result = 0;
        if(root != null){
            result += sumEvenGrandparent(root.left);
            result += sumEvenGrandparent(root.right);
            // 偶数值节点
            if((root.val & 1) != 1){
                result += getNodeSum(root);
            }
        }
        return result;
    }
    int getNodeSum(TreeNode treeNode){
        int result = 0;
        if(treeNode.left != null){
            if(treeNode.left.left != null){
                result += treeNode.left.left.val;
            }
            if(treeNode.left.right != null){
                result += treeNode.left.right.val;
            }
        }
        if(treeNode.right != null){
            if(treeNode.right.left != null){
                result += treeNode.right.left.val;
            }
            if(treeNode.right.right != null){
                result += treeNode.right.right.val;
            }
        }
        return result;
    }
    @Test
    public void test(){
        TreeNode treeNode1 = new TreeNode(6);
        TreeNode treeNode1L = new TreeNode(7);
        TreeNode treeNode1R = new TreeNode(8);
        TreeNode treeNode1LL = new TreeNode(2);
        TreeNode treeNode1LR = new TreeNode(7);
        TreeNode treeNode1RL = new TreeNode(1);
        TreeNode treeNode1RR = new TreeNode(3);
        treeNode1.left = treeNode1L;
        treeNode1.right = treeNode1R;
        treeNode1L.left = treeNode1LL;
        treeNode1L.right = treeNode1LR;
        treeNode1R.left = treeNode1RL;
        treeNode1R.right = treeNode1RR;
        TreeNode treeNode1LLL = new TreeNode(9);
        TreeNode treeNode1LRL = new TreeNode(1);
        TreeNode treeNode1LRR = new TreeNode(4);
        TreeNode treeNode1RRR = new TreeNode(5);
        treeNode1LL.left = treeNode1LLL;
        treeNode1LR.left = treeNode1LRL;
        treeNode1LR.right = treeNode1LRR;
        treeNode1RR.right = treeNode1RRR;
        int grandparent = sumEvenGrandparent(treeNode1);
        System.out.println(grandparent);
    }
}
